Community Detection Algorithm Based on Optimal Partition of Covers
YANG Xuejie1,2, CHEN Jie1, ZHAO Shu1, QIAN Feng1,3, ZHANG Yanping1
1.School of Computer Science and Technology, Anhui University, Hefei 230601
2.School of Computer Science and Technology, Hefei Normal University, Hefei 230601
3.School of Mathematics and Computer Science, Tongling University, Tongling 244061
The overlapped region samples are divided through merging and dividing operation of sets based on the optimal partition concept, and thus the partition achieves minimal error. In this paper, the optimal partition of cover is introduced into the community detection, and a community detection algorithm based on optimal partition of covers(CDA_OPC) is proposed. The problem of community detection is converted to the optimal partition problem for the fixed coverage. In CDA_OPC, the covers can be constructed by utilizing the overlapped relationship between the nodes. Secondly, the optimal approximation of coverage is obtained through the merging and segmentation of covering subsets based on the concept of the optimal partition. Finally, the similarity between communities is calculated, and the multi-granularity community structure is finally formed through multi-level integration. Experimental results on real networks show that CDA _OPC is effective at community detection of networks.
[1] GIRVAN M, NEWMAN M E J. Community Structure in Social and Biological Networks. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12): 7821-7826.
[2] NEWMAN M E J. Detecting Community Structure in Networks. The European Physical Journal B(Condensed Matter and Complex Systems), 2004, 38(2): 321-330.
[3] YANG L, CAO X C, HE D X, et al. Modularity Based Community Detection with Deep Learning // Proc of the 25th International Joint Conference on Artificial Intelligence. New York, USA: ACM, 2016: 2252-2258.
[4] 杜 梅,胡学钢,李 磊,等.基于网络结构极值优化的半监督社团检测方法.模式识别与人工智能, 2015, 28(2): 162-172.
(DU M, HU X G, LI L, et al. Network Structure-Enhanced Extremal Optimization Based Semi-supervised Algorithm for Community Detection. Pattern Recognition and Artificial Intelligence, 2015, 28(2): 162-172.)
[5] FANUEL M, ALAIZ C M, SUYKENS J A K. Magnetic Eigenmaps for Community Detection in Directed Networks. Physical Review E, 2017, 95. DOI: 10.1103/PhysRevE.95.022302.
[6] SU C, JIA X T, XIE X Z, et al. A New Random-Walk Based Label Propagation Community Detection Algorithm // Proc of the IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology. Washington, USA: IEEE, 2015: 137-140.
[7] SHIGA M, TAKIGAWA I, MAMITSUKA H. A Spectral Approach to Clustering Numerical Vectors as Nodes in a Network. Pattern Recognition, 2011, 44(2): 236-251.
[8] 李国朋,潘志松,姚 清,等.融合先验信息的非负矩阵分解社区发现算法.模式识别与人工智能, 2016, 29(7): 608-615.
(LI G P, PAN Z S, YAO Q, et al. Nonnegative Matrix Factorization Algorithm with Prior Information for Community Detection. Pa-ttern Recognition and Artificial Intelligence, 2016, 29(7): 608-615.)
[9] CLAUSET A, NEWMAN M E J, MOORE C. Finding Community Structure in Very Large Networks. Physical Review E, 2004, 70. DOI: 10.1103/PhysRevE.70.066111.
[10] NEWMAN M E J. Fast Algorithm for Detecting Community Structure in Networks. Physical Review E, 2004, 69. DOI: 10.1103/PhysRevE.69.066133.
[11] BLONDEL V D, GUILLAUME J L, LAMBIOTTE R, et al. Fast Unfolding of Community Hierarchies in Large Networks[J/OL]. [2018-03-12]. https://arxiv.org/pdf/0803.0476.pdf.
[12] ARAB M, AFSHARCHI M. Community Detection in Social Networks Using Hybrid Merging of Sub-communities. Journal of Network and Computer Applications, 2014, 40: 73-84.
[13] SAOUD B, MOUSSAOUI A. Community Detection in Networks Based on Minimum Spanning Tree and Modularity. Physica A(Statistical Mechanics and Its Applications), 2016, 460: 230-234.
[14] PAN Y, LI D H, LIU J G, et al. Detecting Community Structure in Complex Networks via Node Similarity. Physica A(Statistical Mechanics and Its Applications), 2010, 389(14): 2849-2857.
[15] WANG T, YIN L Y, WANG X X. A Community Detection Method Based on Local Similarity and Degree Clustering Information. Physica A(Statistical Mechanics and Its Applications), 2018, 490: 1344-1354.
[16] 姜雅文,贾彩燕,于 剑.基于类原型的复杂网络重叠社区发现方法.模式识别与人工智能, 2013, 26(7): 648-659.
(JIANG Y W, JIA C Y, YU J. Overlapping Community Detection in Complex Networks Based on Cluster Prototypes. Pattern Recognition and Artificial Intelligence, 2013, 26(7): 648-659.)
[17] 张新猛,蒋盛益.基于核心图增量聚类的复杂网络划分算法.自动化学报, 2013, 39(7): 1117-1125.
(ZHANG X M, JIANG S Y. Complex Network Community Detection Based on Core Graph Incremental Clustering. Acta Automatica Sinica, 2013, 39(7): 1117-1125.)
[18] RADICCHI F, CASTELLANO C, CECCNI F, et al. Defining and Identifying Communities in Networks. Proceedings of the National Academy of Sciences of the United States of America, 2004, 101(9): 2658-2663.
[19] ZARANDI F D, RAFSANJANI M K. Community Detection in Complex Networks Using Structural Similarity. Physica A(Statistical Mechanics and Its Applications), 2018, 503: 882-891.
[20] 张 铃,王伦文.模糊相容关系的最优逼近问题.计算机学报, 2013, 36(11): 2274-2282.
(ZHANG L, WANG L W. Best Approximation for Fuzzy Tolerance Relation. Chinese Journal of Computers, 2013, 36(11): 2274-2282.)
[21] 王伦文,张贤骥,张 铃.基于模糊相容关系的聚类粒度分析.系统仿真学报, 2014, 26(7): 1492-1496.
(WANG L W, ZHANG X J, ZHANG L. Granular Analysis in Clustering Based on Fuzzy Tolerance Relation. Journal of System Simulation, 2014, 26(7): 1492-1496.)
[22] LI W, HUANG C, WANG X, et al. Stepping Community Detection Algorithm Based on Label Propagation and Similarity. Physica A(Statistical Mechanics and Its Applications), 2017, 472: 145-155.
[23] AHAJJAM S, HADDAD M E, BADIR H. A New Scalable Leader-Community Detection Approach for Community Detection in Social Networks. Social Networks, 2018, 54: 41-49.
[24] STEINHAEUSER K, CHAWLA N V. Identifying and Evaluating Community Structure in Complex Networks. Pattern Recognition Letters, 2010, 31(5): 413-421.
2018, Vol. 31 
